package algorithmTopics.mathematics;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 解决方案
 *
 * @author 86155
 * @date 2025/08/05
 */
public class Solution {

    /**
     * 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x的n次幂 ）。
     *
     * @param x x
     * @param n n n 是一个整数
     * @return double
     */
    public double myPow(double x, int n) {
        //快速幂
        // x^15 = x * x^4 * x^8
        double ans = 1D;
        if (n < 0D) {
            n = -n;
            x = 1D / x;
        }
        while (n != 0) {
            //移动N 看二进制的最后一位有一就是需要相乘的数字
            if ((n & 1) == 1) {
                ans *= x;
            }
            //自身的平方
            x *= x;
            n >>>= 1;
        }

        return ans;
    }


    /**
     * 平均值 去掉最高和最低
     *
     * @param salary 工资
     * @return double
     */
    public double average(int[] salary) {
        Arrays.sort(salary);
        long sum = 0;
        int len = salary.length;
        for (int i = 1; i < len - 1; i++) {
            sum += salary[i];
        }
        return sum / (len - 2.0);
    }

    /**
     * 计数俩数字之间的计数 ,双闭区间
     *
     * @param low  低
     * @param high 高
     * @return int
     */
    public int countOdds(int low, int high) {
        // 有多少个数字
        int nums = high - low + 1;
        if (nums % 2 == 0) {
            //奇数和偶数一样多
            return nums / 2;
        }
        if (low % 2 == 0) {
            //说明第一个不是奇数
            return (nums - 1) / 2;
        }
        return (nums + 1) / 2;
    }

    //罗马数字转换
    //给出一个罗马数字 返回他所表示的十进制数字
    /*
     *
     * 基本数字 Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个；
     * 2.不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
     * */

    public int romanToInt(String s) {
        // 结果
        int res = 0;
        //一次对比两位
        //如果当前一个字符是大于等于当前的，就是加
        //否则就是减法
        int pre = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int now = getValue(s.charAt(i));
            if (pre >= now) {
                res += pre;
            } else {
                res -= pre;
            }
            pre = now;
        }
        return res += pre;
    }

    //辅助判断罗马数字
    private int getValue(char ch) {
        switch (ch) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }


    // 判断是不是三的幂次方
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }


    //给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：
    public List<String> fizzBuzz(int n) {
        List<String> strings = new ArrayList<>(n);
        for (int i = 1; i < n + 1; i++) {
            strings.add(String.valueOf(i));
        }
        for (int i = 2; i < n; i += 3) {
            strings.set(i, "Fizz");
        }
        for (int i = 4; i < n; i += 5) {
            strings.set(i, "Buzz");
        }
        for (int i = 14; i < n; i += 15) {
            strings.set(i, "FizzBuzz");
        }
        return strings;

    }

    //筛选出素数
    // 试除法 方法一 超时
    private boolean trialDivision(int n) {
        if (n < 2) {
            return false;
        }
        // 小于根号的原因是因为，一个数一定是他根号的平方，也一定是一个小于 他更好和大于他更好的数相乘得到
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    //方法二 埃氏筛 核心 合数 是素数的倍数
//    public int countPrimes(int n) {
//        int count = 0;
//        // 默认是false:表示是素数
//        boolean[] booleans = new boolean[n];
//
//        for (int i = 2; i <= Math.sqrt(n); i++) {
//            //当前的数是素数
//            if (trialDivision(i)) {
//                //把他的倍数都标记为合数 精妙之处 是从i*i开始的
//                for (int j = i*i; j < n; j+=i) {
//                    booleans[j] = true;
//                }
//            }
//
//        }
//        for (int i = 2; i < n; i++) {
//            if (!booleans[i]) {
//                count++;
//            }
//        }
//        return count;
//    }

    //方法三，线性筛 欧拉筛，因为埃氏筛 有一些重复标记
    //核心思想：大于1的正整数，都可以分解为有限个质数相乘
    //每个合数，都有一个最小的质因子 ，通过最小质因子取筛选
    public int countPrimes(int n) {
        int count = 0;
        // 默认是false:表示是素数
        boolean[] booleans = new boolean[n];
        //存储质数
        int[] primes = new int[n];
        int index = 0;
        for (int i = 2; i < n; i++) {
            //当前的数是素数
            if (!booleans[i]) {
                count++;
                primes[index++] = i;
                //把他的倍数都标记为合数 精妙之处 是从i*i开始的
            }
            for (int j = 0; j < index && i * primes[j] < n; j++) {
                booleans[i * primes[j]] = true;
                if (i % primes[j] == 0) {
                    break;
                }
            }

        }

        return count;
    }


//
//    public int countPrimes(int n) {
//        int count = 0;
//        for (int i = 0; i < n ; i++) {
//            if (trialDivision(i)) {
//                count++;
//            }
//        }
//
//        return count;
//    }
}
